#include <stdio.h>

 /* 快速排序：
// * 前提：从小到大进行排序 用数组来存储
// * 核心思想：
// * （1）每次遍历时选取一个中间元素 ============>选元素，一般选第一个
// * （2）将大于中间元素的值全部放到中间元素的右边 =========>右子集
// * （3）小于的放到左边 ========>左子集
// * (4)然后对左右子集进行上述操作。 ===========>递归算法
// *
// * 划分操作：
// *      1.选第一个元素作为中间值pivot
// *      2.设置两个左右指针分别指向数组的左边和右边
// *      3.先移动右指针，直到遇到不对的元素（小于pivot的元素），将该元素移动到左边的空位置
// *      4.再移动左指针，直到遇到不对的元素（大于pivot的元素），将该元素移动到右边的空位置
// *      5.循环上述操作，直到左右指针相遇
// */
//
////划分操作 返回中间元素最后放置的下标值
int partition(int arr[],int left,int right){
//    //1.选取第一个值作为中间元素
    int mid=arr[left];
    //2.left和right分别是左右指针，不需要单独设置
    //3.循环移动左右指针
    while(left<right){
        //3.1先移动右指针
        while(left<right&& arr[right]>mid){
            right --;
       }
        arr[left]=arr[right];
        while(left<right&& arr[left]<mid){
            left ++;
       }
       arr[right]=arr[left];
    }
    arr[left]=mid;
    return left;
}


// * 函数名：quickSort
// * 输入：无序的数组arr,数组的左右位置
// * 输出：无
// */
void quickSort(int arr[],int left,int right){
    //对数组排序，前提数组里至少包含2个元素
    if(left<right){
        //1.划分
        int midPos= partition(arr,left,right);
        //2.递归
        quickSort(arr,left,midPos-1);
        quickSort(arr,midPos+1,right);
    }
}
int main() {
    int arr[5]={45,23,12,145,234};
    quickSort(arr,0,4);
    return 0;
}



